package simple;

import java.util.LinkedList;

/**
 * 14. 最长公共前缀
 *
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * 如果不存在公共前缀，返回空字符串 ""。
 *
 * 示例 1:
 *
 * 输入: ["flower","flow","flight"]
 * 输出: "fl"
 * 示例 2:
 *
 * 输入: ["dog","racecar","car"]
 * 输出: ""
 * 解释: 输入不存在公共前缀。
 * 说明:
 * 所有输入只包含小写字母 a-z 。
 * */
public class LongestCommonPrefix {
    // 横向扫描 时间复杂度：O(mn) m是字符串数组中的字符串的平均长度 n是字符串数量
    // 空间复杂度：O(1)
    public String longestCommonPrefix(String[] strs){
        if(strs.length < 1 || strs == null){
            return "";
        }
        String result = strs[0];
        int i = 1;
        while(i < strs.length){
            result = getLongestCommonPrefix(result, strs[i]);
            if(result.length() == 0) return "";
            i++;
        }

        return result;
    }

    // 获取s1和s2的最长公共前缀
    public String getLongestCommonPrefix(String s1, String s2){
        int i = 0;
        int len = Math.min(s1.length(), s2.length());
        while(i < len && s1.charAt(i) == s2.charAt(i)) i++;
        return s1.substring(0,i);
    }

    // 纵向扫描 时间复杂度：O(mn)  空间复杂度：O(1)
    /**
     * 取到第一个字符串 然后比对其他每个字符串的相同位置上的字符
     *
     * */
    public String longestCommonPrefix1(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int len = strs[0].length();
        int count = strs.length;
        for (int i = 0; i < len; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < count; j++) {
                // 如果j条字符串长度为i 或者 相同位置上字符不一样 那么就返回前缀即可
                if(i == strs[j].length() || c != strs[j].charAt(i)){
                    return strs[0].substring(0,i);
                }
            }
        }
        return strs[0];
    }


    // main
    public static void main(String[] args) {
        LongestCommonPrefix lcp = new LongestCommonPrefix();
        String r = lcp.longestCommonPrefix1(new String[]{"flower","flow","flight"});
        System.out.print(r);
    }
}
